class Task49:
    def run(self, n):
        if n <= 0:
            return None

        ugly_numbers = [0 for _ in range(n)]
        ugly_numbers[0] = 1

        index_x2 = 0
        index_x3 = 0
        index_x5 = 0
        for i in range(1, n):
            ugly_numbers[i] = min(
                ugly_numbers[index_x2] * 2,
                ugly_numbers[index_x3] * 3,
                ugly_numbers[index_x5] * 5
            )
            while ugly_numbers[index_x2] * 2 <= ugly_numbers[i]:
                index_x2 += 1
            while ugly_numbers[index_x3] * 3 <= ugly_numbers[i]:
                index_x3 += 1
            while ugly_numbers[index_x5] * 5 <= ugly_numbers[i]:
                index_x5 += 1

        return ugly_numbers[-1]


class Task49Old:
    def run(self, n):
        num = 1
        count = 0
        while True:
            if self.is_ugly(num):
                count += 1
                if count == n:
                    return num
            num += 1

    def is_ugly(self, n):
        while n % 2 == 0:
            n = n // 2
        while n % 3 == 0:
            n = n // 3
        while n % 5 == 0:
            n = n // 5
        return n == 1
